package com.gxc.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 完全二叉树   除了最后一层玩，其他层节点满，且最后一层有右节点的必有左节点
 */
public class CompleteBinaryTree {

    public static void main(String[] args) {
        TreeBean tree = Preorder.createNoCompleteBinaryTree();
        TreeBean tree2 = Preorder.createTree();

        System.out.println("----------");
        Stack<TreeBean> stack = new Stack<>();
        //非递归判断是否完全二叉树
        System.out.println(nonRecursion(tree));
        System.out.println(nonRecursion(tree2));
    }

    /**
     * 非递归判断是否完全二叉树
     * @param tree
     * @return
     */
    private static boolean nonRecursion(TreeBean tree) {
        Queue<TreeBean> queue = new LinkedList<>();
        queue.add(tree);
        //第一个没有左右子节点的节点
        boolean firstNoChildNode = false;
        while (!queue.isEmpty()) {
            TreeBean treeBean = queue.poll();
            //有右节点的必有左节点
            if (treeBean.right!=null && treeBean.left == null) return false;
            if (firstNoChildNode) {
                if (treeBean.right!=null || treeBean.left != null) return false;
            }
            if (treeBean.right ==null || treeBean.left == null) {
                firstNoChildNode = true;
            }
            if (treeBean.left!=null) queue.add(treeBean.left);
            if (treeBean.right!=null) queue.add(treeBean.right);
        }
        return true;
    }


}
